public class Solution91 {
    public int numDecodings(String s) {
        int[] f=new int[s.length()+1];
        f[0]=1;
        for (int i=0;i<s.length();i++){
            if (s.charAt(i)!='0') {
                f[i+1]=f[i];
            }
            if (i>0 && (s.charAt(i-1)=='1' || s.charAt(i-1)=='2' && s.charAt(i)>='0' && s.charAt(i)<='6')){
                f[i+1]+=f[i-1];
            }
        }
        return f[s.length()];
    }

    public static void main(String[] args) {
        System.out.println(new Solution91().numDecodings("06"));
    }
}
